package gold.gold04;

import java.util.Arrays;

/**
 * 别人答案看一下。
 *
 * 个人认为回溯也是相当于用一种可快速中止(前面不行了后面不用举例了)的方式穷举了一大堆情况,
 * 甚至对于本题而言, 回溯和穷举是一样的效果。
 */
public class S0813堆箱子 {
    /**
     * 17, 落泪。
     * 动态规划最重要的就是找到递推的关系, 这一题的关系就是, 在可以堆的前提下, 当前箱子可以堆成的高度 = 前面可堆成的高度+当前箱子的高度
     * 只要确定当前箱子的上一个箱子就行了, 对于它再往上的我们就不用关心了。
     * 根据别人思路, 先按照其中一维排序, 然后动态规划
     * Arrays.sort(box, (int[] x, int[] y)->x[2] - y[2]);这个得到的是一个升序的结果
     */
    public int pileBox3(int[][] box) {
        int[] record = new int[box.length];
        // 我们获取一个升序, 然后记录每个位置以当前点为底可以得到的最高摆放, 注意这个排序, 不光是按照一个值
        // 这样的话在这个点后面的盒子是绝对不可能摆在这个点上面的
        Arrays.sort(box, (int[] x, int[] y)->x[2] == y[2]?(x[1] == y[1]?x[0] - y[0]: x[1] - y[1]): x[2] - y[2]);
        //这个很重要, 因为可能它前面没有能放在他上面的盒子
        for(int i = 0; i < box.length; i ++){
            record[i] = box[i][2];
        }
        for(int i = 1; i < box.length; i ++){
            for(int j = 0; j < i; j++){
                if(box[j][0] < box[i][0] & box[j][1] < box[i][1] & box[j][2] < box[i][2])
                    record[i] = Math.max(record[i], record[j] + box[i][2]);
            }
        }
        int maxSum = 0;
        for(int i: record){
            if(i > maxSum) maxSum = i;
        }
        return maxSum;
    }

    /**
     * 排序之后再回溯, 好像复杂度和直接回溯没什么区别
     * 这个在一部分长测试用例上结果不对。应该是因为按照排序不光是需要按照一个值, 考虑到值相同的情况, 三个值都要用上
     */
    int maxSum;
    public int pileBox2(int[][] box) {
        //record = new int[box.length];
        // 只返回一个值就省略return, 然后这样会得到一个降序, 问题转化为求这个新的序列的一个符合下大上小的和最大的子序列
        Arrays.sort(box, (int[] x, int[] y)->y[2] - x[2]);
        findMaxSub(new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE}, box, 0, 0);
        return maxSum;
    }
    private void findMaxSub(int[] preBox, int[][] box, int curLoc, int preSum){
        //System.out.println(Arrays.toString(preBox) + curLoc + " " + preSum);
        if(curLoc == box.length) return;
        // 当前点在子序列中, 高度已经递增了, 比较前两个就行
        if(box[curLoc][0] < preBox[0] & box[curLoc][1] < preBox[1]){
            //record[curLoc] = 1;
            maxSum = Math.max(maxSum, preSum + box[curLoc][2]);
            findMaxSub(box[curLoc], box, curLoc + 1, preSum + box[curLoc][2]);

        }
        // 当前点不在子序列中
        findMaxSub(preBox, box, curLoc + 1, preSum);
    }


    /**
     * 试一下回溯, 在数据大的时候超时了
     * 注意java的二维数组也是a[1][2]这样取值的
     */
    int[] record;// 记录每个箱子是否已被使用
    //int maxSum = 0;
    public int pileBox(int[][] box) {
        if(box == null || box.length == 0) return 0;
        record = new int[box.length];

        int[] initBox = new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE};
        findMaxSum(initBox, box, 0);
        return maxSum;
    }
    private void findMaxSum(int[] preBox, int[][] box, int preSum){
        for(int i = 0; i < record.length; i++){
            if(record[i] == 0){// 这个箱子还没用过
                if(box[i][0] < preBox[0] && box[i][1] < preBox[1] && box[i][2] < preBox[2]){
                    record[i] = 1;
                    int tempLen = preSum + box[i][2];
                    maxSum = Math.max(maxSum, tempLen);
                    findMaxSum(box[i], box, tempLen);
                    record[i] = 0;
                }
            }
        }
    }


}
